#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

//int n, m;
//
//const int N = 1e5 + 10;
//long long int a[N], f[N];
//
//int l, r;
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        f[i] = f[i - 1] + a[i];
//    }
//
//    for (int i = 0; i < m; i++)
//    {
//        cin >> l >> r;
//        cout << f[r] - f[l - 1] << endl;
//    }
//
//    return 0;
//}

//int n;
//
//const int N = 1e6 + 10;
//
//int a[N], f[N], g[N];
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//
//	int prev = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		f[i] = f[i - 1] + a[i];
//		g[i] = f[i] - prev;
//		prev = min(prev, f[i]);
//	}
//
//	
//
//	int _max = INT_MIN;
//	for (int i = 1; i <= n; i++)
//	{
//		_max = max(_max, g[i]);
//	}
//
//	cout << _max;
//
//
//
//	return 0;
//}



//int n, m, q, x1, y1, x2, y2;
//const int N = 1e4 + 10;
//long long int a[N][N];
//long long int f[N][N];
//
//int main()
//{
//    cin >> n >> m >> q;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//        }
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
//        }
//    }
//
//    for (int k = 0; k < q; k++)
//    {
//        cin >> x1 >> y1 >> x2 >> y2;
//        cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] 
// + f[x1 - 1][y1 - 1] << endl;
//    }
//
//    return 0;
//}

//const int N = 5015;
//
//int a[N][N], f[N][N], x, y, v;
//
//int n, m;
//int main()
//{
//	cin >> n >> m;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> x >> y >> v;
//		a[x + 1][y + 1] += v;
//	}
//
//	for (int i = 1; i <= 5010; i++)
//	{
//		for (int j = 1; j <= 5010; j++)
//		{
//			f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
//		}
//	}
//
//	int _max = INT_MIN;
//
//	
//
//	for (int i = 5014; i >= m; i--)
//	{
//		for (int j = 5014; j >= m; j--)
//		{
//			int x2 = i - m + 1;
//			int y2 = j - m + 1;
//			if (x2 < 0)
//				x2 = 1;
//			if (y2 < 0)
//				y2 = 1;
//			_max = max(_max, f[x2][y2] - f[i - 1][y2] - f[x2][j - 1]
//				+ f[i - 1][j - 1]);
//		}
//	}
//
//	cout << _max;
//
//	return 0;
//
//}